#include <iostream>
using namespace std;

template <class dato>
class conjAc
{
	public:
		conjAc(const int limite);
		conjAc(const conjAc& );
		conjAc();
		~conjAc();
		void Ag(const dato elem);
		bool pertenece(const dato elem) const;
		void sinUno();
		dato dameUno() const;
		int cardinal() const;
		
		// Operadores varios
		void operator=(const conjAc<dato>&);
		bool operator==(const conjAc<dato>&) const;
		bool operator!=(const conjAc<dato>&) const;
		template<class dato2> 
		friend ostream& operator<<(ostream &salida, const conjAc<dato2> &c2);


	private:
		dato* array;
		int ultimaPosUsada;
};

template<class dato>
conjAc<dato>::conjAc() {
	this->array = NULL;
	this->ultimaPosUsada = 0;
};

template<class dato>
conjAc<dato>::conjAc(const int limite) {
	this->ultimaPosUsada = 0;
	this->array = new dato[limite];	
};


template<class dato>
conjAc<dato>::~conjAc() {
	delete[] this->array;
	this->ultimaPosUsada = 0;
};

template<class dato>
void conjAc<dato>::Ag(const dato elem) {
	int indice = 0;
	bool noTermine = true;
	int padre = 0;
	dato elemAux;
	
	this->array[this->ultimaPosUsada] = elem;
	indice = this->ultimaPosUsada;
	while( indice > 0 && noTermine) {
		//primero veo quien seria el padre de este elemento
		if (indice % 2 == 0) {
			//en este caso estoy parado sobre el nodo derecho
			padre = (indice-2) /2;
		}
		else {
			//en este caso estoy parado sobre el nodo izquierdo
			padre = (indice-1) /2;
		};
		//ahora veo si intercambio los valores
		if (this->array[indice] < this->array[padre]) {
			//entonces tengo que intercambiar los valores
			elemAux = this->array[indice];
			this->array[indice] = this->array[padre];
			this->array[padre] = elemAux;
		}
		else {
			//sino intercambio, ese dato, termine de hacer el ciclo
			noTermine = false;
		};
		//acutalizo el valor del indice
		indice = padre;
	}
	this->ultimaPosUsada++;
};




template<class dato>
bool conjAc<dato>::pertenece(const dato elem) const{
	int indice = 0;
	bool noTermine = true;
	bool res = false;
	
	//busco en todo el arreglo, en donde esta definido ese valor
	while (indice < this->ultimaPosUsada && noTermine)
	{
		if (this->array[indice] == elem) {
			res = true;
			noTermine = false;
		}
		else 
		{
				indice++;
		}
	}
	
	return res;	
};

template<class dato>
dato conjAc<dato>::dameUno() const {
	return this->array[0];
};

template<class dato>
int conjAc<dato>::cardinal() const {
	if (this->ultimaPosUsada == 0)
	{
		return 0;
	}
	else 
	{
		return this->ultimaPosUsada;
	}
	
	
};
	
template<class dato>
void conjAc<dato>::sinUno() {
	int indice = 0;
	bool noTermine;
	bool soloEsteDefinidoElHijoIzq;
	bool estanDefinidoLosDosHijos;
	dato elementoAux;
	
	//primero subo el ultimo valor a la primera posicion
	this->array[0] = this->array[this->ultimaPosUsada-1];
	this->ultimaPosUsada--;
	noTermine = true;

	while (noTermine)
	{
		//me fijo si tiene los dos hijos definidos la posicion actual
		soloEsteDefinidoElHijoIzq = (2*indice+1 <= this->ultimaPosUsada);
		estanDefinidoLosDosHijos = soloEsteDefinidoElHijoIzq && (2*indice+2 <= this->ultimaPosUsada);
		
		
		//si tiene los dos hijos definidos, me fijo por cual reemplazar
		if (estanDefinidoLosDosHijos)
		{
			//me fijo si la raiz del hijo der es menor que la raiz actual, y au su veez que la raiz
			//del hijo izq es menor que la raiz del hijo der
			if (this->array[2*indice+2] < this->array[indice] && this->array[2*indice+2] < this->array[2*indice+1])
			{
				elementoAux = this->array[2*indice+2];
				this->array[2*indice+2] = this->array[indice];
				this->array[indice] = elementoAux;
				indice = indice*2+2;
			}
			//me fijo si la  raiz del hijo izq es menor que la raiz actual, y a su vez
			//que la raiz del hijo der es menor que la raiz del hijo izq
			else if (this->array[2*indice+1] < this->array[indice] && this->array[2*indice+1] < this->array[2*indice+2]) 
			{
				elementoAux = this->array[2*indice+1];
				this->array[2*indice+1] = this->array[indice];
				this->array[indice] = elementoAux;
				indice = 2*indice+1;
				
			}
			else 
			{
				// sino es ninguno de los dos casos anteriores, entonces termine porque no puedo
				//intercambiar mas valores
				noTermine = false;
			}
		}
		//Si solo tiene el hijo izquierdo definido, entonces me fijo si lo reemplazo
		else if (soloEsteDefinidoElHijoIzq) {
			if (this->array[2*indice+1] < this->array[indice])
			{
				elementoAux = this->array[2*indice+1];
				this->array[2*indice+1] = this->array[indice];
				this->array[indice] = elementoAux;
				indice = indice*2+1;
			}
			else {
				noTermine = false;
			};
		}
		//Sino tiene ninguno de los hijos definidos, entonces es una hoja
		else {
			noTermine = false;
		};
	};
};

/********************************************************************
Funciones que no estaban en el diseño pero que se necesitan para C++
***********************************************************************/
template<class dato>
void conjAc<dato>::operator=(const conjAc<dato>& cAux) {
	int indice = 0;
	this->array = new dato[cAux.ultimaPosUsada];
	while (indice < cAux.ultimaPosUsada) {
		this->array[indice] = cAux.array[indice];
		indice++;
	};
	this->ultimaPosUsada = cAux.ultimaPosUsada;
}

template<class dato>
bool conjAc<dato>::operator==(const conjAc<dato>& cAux) const {
	bool res;
	int indice = 0;
	res = (this->ultimaPosUsada == cAux.ultimaPosUsada);
	if (res) {
		while (indice < this->ultimaPosUsada && res) {
			res = (this->array[indice] == cAux.array[indice]);
			indice++;
		};
	};
	return res;
};

	
template<class dato2> 
ostream& operator<<(ostream &salida, const conjAc<dato2> &cAux) {
	conjAc<dato2> c2(cAux);
	salida << "[ "<< c2.cardinal();
	while (c2.cardinal() > 0) 
	{
		salida << " , " << c2.dameUno();
		c2.sinUno();
	};
	salida << " ] ";
	return salida;
};
		
template<class dato>
conjAc<dato>::conjAc(const conjAc<dato>& conjAux) {
	int indice = 0;
	this->array = new dato[conjAux.ultimaPosUsada];
	this->ultimaPosUsada = conjAux.ultimaPosUsada;
	
	while (indice < conjAux.ultimaPosUsada) {
		this->array[indice] = conjAux.array[indice];
		indice++;
	};
};
	
	
		
